import java.util.*;

public class Test {
    /*
    题目1：最小覆盖子串
     */
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        int[] hash1 = new int[128];
        int kinds = 0;
        for(char x : t){
            if(hash1[x] == 0) kinds++;
            hash1[x]++;
        }

        int[] hash2 = new int[128];
        int minlen = Integer.MAX_VALUE, begin = -1;

        for(int left = 0, right = 0, count = 0; right < s.length; right++){
            char in = s[right];
            hash2[in]++;

            if(hash2[in] == hash1[in]){
                count++;
            }

            while(count == kinds){
                if(right - left + 1 < minlen){
                    minlen = right - left + 1;
                    begin = left;
                }

                char out = s[left++];
                if(hash1[out] == hash2[out]--) count--;

            }
        }
        if(begin == -1) return new String();
        else return ss.substring(begin, begin + minlen);
    }

    /*
    题目2：重复的 DNA 序列
     */
    // 暴力枚举
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> list = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();

        for(int i = 0; i + 10 <= s.length(); i++){
            String sub = s.substring(i, i + 10);
            map.put(sub, map.getOrDefault(sub, 0) + 1);

            // 防止多次添加元素！
            if(map.get(sub) == 2){
                list.add(sub);
            }
        }
        return list;
    }

    /*
    题目3：二分查找
     */
    public int search(int[] nums, int target) {
        int n = nums.length;

        int left = 0;
        int right = n - 1;

        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }

    /*
    题目 4：在排序数组中查找元素的第一个和最后一个位置
     */
    public int[] searchRange(int[] nums, int target) {
        int[] arr = new int[2];
        arr[0] = arr[1] = -1;
        int n = nums.length;
        if(n == 0){
            return arr;
        }

        // 查找左端点
        // 划分成
        // < 以及 >=
        int left = 0;
        int right = n - 1;

        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        if(nums[right] != target){
            return arr;
        }else{
            arr[0] = right;
        }


        left = 0;
        right = n - 1;
        // 查找右端点
        // 划分成
        // > 以及 <=
        while(left < right){
            int mid = left + (right - left + 1)/2;
            if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid;
            }
        }
        arr[1] = right;
        return arr;
    }

    

}
